Bellman-Ford in Almost-Linear Time for Dense Graphs
March 25, 2026 (GHC 8102)
I will present an n^2 time algorithm for single-source shortest paths with negative real weights, building on the breakthrough work of Fineman (STOC 2024). The talk will be entirely self-contained and only assume basic probability facts.
Based on joint work with Jason Li, Satish Rao, and Junkai Zhang.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.